{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Product of Array Except Self"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: productExceptSelf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #除自身以外数组的乘积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>，返回 <em>数组&nbsp;<code>answer</code>&nbsp;，其中&nbsp;<code>answer[i]</code>&nbsp;等于&nbsp;<code>nums</code>&nbsp;中除&nbsp;<code>nums[i]</code>&nbsp;之外其余各元素的乘积</em>&nbsp;。</p>\n",
    "\n",
    "<p>题目数据 <strong>保证</strong> 数组&nbsp;<code>nums</code>之中任意元素的全部前缀元素和后缀的乘积都在&nbsp; <strong>32 位</strong> 整数范围内。</p>\n",
    "\n",
    "<p>请&nbsp;<strong>不要使用除法，</strong>且在&nbsp;<code>O(<em>n</em>)</code> 时间复杂度内完成此题。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = <code>[1,2,3,4]</code>\n",
    "<strong>输出:</strong> <code>[24,12,8,6]</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [-1,1,0,-3,3]\n",
    "<strong>输出:</strong> [0,0,9,0,0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-30 &lt;= nums[i] &lt;= 30</code></li>\n",
    "\t<li><strong>保证</strong> 数组&nbsp;<code>nums</code>之中任意元素的全部前缀元素和后缀的乘积都在&nbsp; <strong>32 位</strong> 整数范围内</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以在 <code>O(1)</code>&nbsp;的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组&nbsp;<strong>不被视为&nbsp;</strong>额外空间。）</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [product-of-array-except-self](https://leetcode.cn/problems/product-of-array-except-self/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [product-of-array-except-self](https://leetcode.cn/problems/product-of-array-except-self/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]', '[-1,1,0,-3,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        cul = 1\n",
    "        for num in nums:\n",
    "            res.append(cul)\n",
    "            cul *= num\n",
    "        \n",
    "        cul = 1\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            res[i] = res[i] * cul\n",
    "            cul *= nums[i]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        zero = 0\n",
    "        s = 1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                if zero == 1:\n",
    "                    return [0 for _ in range(len(nums))]\n",
    "                zero = zero + 1\n",
    "                continue\n",
    "            s = s * nums[i]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                nums[i] = s\n",
    "            else:\n",
    "                if zero == 1:\n",
    "                    nums[i] = 0\n",
    "                else:\n",
    "                    nums[i] = int(s/nums[i])\n",
    "        return nums\n",
    "            \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        multi_all = 1\n",
    "        len_nums = len(nums)\n",
    "        count_zero = len_nums\n",
    "        for i in range(len_nums):\n",
    "        \tif nums[i] != 0:\n",
    "        \t\tmulti_all *= nums[i]\n",
    "        \t\tcount_zero -= 1\n",
    "        \n",
    "        result = []\n",
    "        if count_zero > 1: \n",
    "        \treturn [0] * len_nums\n",
    "        elif count_zero == 1:\n",
    "        \tfor x in nums:\n",
    "        \t\tif x == 0: \n",
    "        \t\t\tresult.append(multi_all)\n",
    "        \t\telse:\n",
    "        \t\t\tresult.append(0)\n",
    "        else:        \n",
    "\t        for x in nums:\n",
    "\t        \tresult.append(multi_all//x)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        r = [1] * n\n",
    "        for i in range(1, n):\n",
    "            r[i] = r[i - 1] * nums[i - 1]\n",
    "        prod_right = 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            prod_right *= nums[i + 1]\n",
    "            r[i] *= prod_right\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        out=[]\n",
    "        p=1\n",
    "        for i in nums:\n",
    "            out.append(p)\n",
    "            p*=i\n",
    "        p=1\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            out[i]*=p\n",
    "            p*=nums[i]\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\r\n",
    "        res = [0] * len(nums)\r\n",
    "        tmp = {}\r\n",
    "        for i in range(len(res)):\r\n",
    "            num = 1\r\n",
    "            if nums[i] in tmp:\r\n",
    "                res[i] = tmp[nums[i]]\r\n",
    "                continue\r\n",
    "            for j in range(len(nums)):\r\n",
    "                if i==j:\r\n",
    "                    continue\r\n",
    "                num *= nums[j]\r\n",
    "            res[i] = num\r\n",
    "            tmp[nums[i]] = num\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        dp=[0]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if i-1>=0 and nums[i]==nums[i-1]:\n",
    "                dp[i]=dp[i-1]\n",
    "            elif nums[i] in nums[0:i]:\n",
    "                add=nums[0:i].index(nums[i])\n",
    "                dp[i]=dp[add]\n",
    "            else:\n",
    "                res=1\n",
    "                for j in range(len(nums)):\n",
    "                    if j!=i:\n",
    "                        res=res*nums[j]\n",
    "                dp[i]=res\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        re=[1]*n\n",
    "        re[n-1]=1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            re[i]=re[i+1]*nums[i+1]\n",
    "        t=nums[0]\n",
    "        nums[0]=1\n",
    "        for i in range(1,n):\n",
    "            u=nums[i]\n",
    "            nums[i]=t*nums[i-1]\n",
    "            t=u\n",
    "        for i in range(n):\n",
    "            re[i]*=nums[i]\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        x = [0]*len(nums)\n",
    "        d = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in d:\n",
    "                x[i]=d[nums[i]]\n",
    "            else:\n",
    "                n=1\n",
    "                for j in range(len(nums)):\n",
    "                    if i!=j:\n",
    "                        n*=nums[j]\n",
    "                x[i]=n\n",
    "                d[nums[i]]=n\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        l = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in nums[:i]:\n",
    "                l.append(l[nums.index(nums[i])])\n",
    "            else:\n",
    "                l.append(reduce(lambda x,y:x*y,nums[0:i]+nums[i+1:]))\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        n= len(nums)\n",
    "        ans = [1] * n\n",
    "        left = right = 1\n",
    "        for i in range(n):\n",
    "            ans[i] *= left\n",
    "            ans[n-1-i] *= right\n",
    "            left *= nums[i]\n",
    "            right *= nums[n-1-i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        right = 1\n",
    "        nums1 = []\n",
    "        current = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            nums1.append(num)\n",
    "            if i > 0:\n",
    "                nums[i] *= nums[i-1]\n",
    "            current = i\n",
    "        while current > 0:\n",
    "           \n",
    "            nums[current] = nums[current-1]*right\n",
    "            right *=  nums1[current]\n",
    "            current -= 1\n",
    "        nums[0] = right\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        n,res=len(nums),[]\n",
    "        hash_map=dict()\n",
    "        for index,value in enumerate(nums):\n",
    "            if value in hash_map:\n",
    "                res.append(hash_map[value])\n",
    "            else:\n",
    "                cur = nums[index]\n",
    "                nums[index] = 1\n",
    "                hash_map[value]=reduce(lambda x, y: x * y, nums)\n",
    "                res.append(hash_map[value])\n",
    "                nums[index] = cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0] * len(nums)\n",
    "        if nums.count(0) > 1:\n",
    "            return ans\n",
    "        elif nums.count(0) > 0:\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] == 0:\n",
    "                    ans[i] = 1\n",
    "                    for num in nums:\n",
    "                        if num != 0:\n",
    "                            ans[i] *= num\n",
    "                    return ans\n",
    "\n",
    "        # non zero\n",
    "        calculated = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in calculated:\n",
    "                ans[i] = calculated[nums[i]]\n",
    "            else:\n",
    "                ans[i] = 1\n",
    "                for j in range(len(nums)):\n",
    "                    if j != i:\n",
    "                        ans[i] *= nums[j]\n",
    "                calculated[nums[i]] = ans[i]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        l,re,hashm=len(nums),[],{}\n",
    "        for i in range(l):\n",
    "            c,sums=True,1\n",
    "            if nums[i] in hashm:\n",
    "                    c=False\n",
    "                    re.append(hashm[nums[i]])\n",
    "                    continue \n",
    "            for j in range(l):              \n",
    "                if i==j:continue\n",
    "                elif nums[j]==1:continue\n",
    "                elif nums[j]==0:sums=0\n",
    "                else:\n",
    "                    sums=sums*nums[j]\n",
    "            if c:\n",
    "                hashm[nums[i]]=sums\n",
    "                re.append(sums)\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from operator import mul\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        other = nums.copy()\n",
    "        ans = []\n",
    "        hash_other = {}\n",
    "        for i, item in enumerate(nums):\n",
    "            if hash_other.get(item, False):\n",
    "                _res = hash_other[item]\n",
    "            else:\n",
    "                other.pop(i)\n",
    "                _res = reduce(mul, other)\n",
    "                hash_other[item] = _res\n",
    "                other.insert(i, item)\n",
    "            ans.append(_res)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        zero_index = -1\n",
    "        a = [0] * 61\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == 0:\n",
    "                if zero_index == -1:\n",
    "                    zero_index = i\n",
    "                else:\n",
    "                    return [0] * len(nums)\n",
    "            a[x + 30] += 1\n",
    "        \n",
    "        @cache\n",
    "        def f(x):\n",
    "            return reduce(lambda x, y: x * y, [pow(i, v - int(x == i)) for i, v in enumerate(a, -30)])\n",
    "\n",
    "        if zero_index != -1:\n",
    "            ans = [0] * len(nums)\n",
    "            ans[zero_index] = f(0)\n",
    "            return ans\n",
    "        return [f(x) for x in nums]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        zero_index = -1\n",
    "        a = [0] * 61\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == 0:\n",
    "                if zero_index == -1:\n",
    "                    zero_index = i\n",
    "                else:\n",
    "                    return [0] * len(nums)\n",
    "            a[x + 30] += 1\n",
    "        \n",
    "        @cache\n",
    "        def f(x):\n",
    "            ret = 1\n",
    "            for i, v in enumerate(a, -30):\n",
    "                ret *= pow(i, v - int(x == i))\n",
    "            return ret\n",
    "\n",
    "        if zero_index != -1:\n",
    "            ans = [0] * len(nums)\n",
    "            ans[zero_index] = f(0)\n",
    "            return ans\n",
    "        return [f(x) for x in nums]\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        zero = 0\n",
    "        res = 1\n",
    "        for i in nums:\n",
    "            if i == 0:\n",
    "                zero += 1\n",
    "            else:\n",
    "                res = res*i\n",
    "        for i in range(len(nums)):\n",
    "            if zero >= 2 :\n",
    "                nums[i] = 0\n",
    "            elif zero == 1:\n",
    "                if nums[i] == 0:\n",
    "                    nums[i] = res\n",
    "                else :\n",
    "                    nums[i] = 0\n",
    "            else:\n",
    "                nums[i] =int(res/nums[i]) \n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        answer = []\n",
    "        # 相同的数可以跳过\n",
    "        answer_map = {}\n",
    "        size = len(nums)\n",
    "        for i in range(size):\n",
    "            if nums[i] in answer_map:\n",
    "                answer.append(answer_map[nums[i]])\n",
    "                continue\n",
    "            mult = 1\n",
    "            for j in range(size):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if nums[j] == 0:\n",
    "                    mult = 0\n",
    "                    break\n",
    "                mult *= nums[j]\n",
    "            answer.append(mult)\n",
    "            answer_map[nums[i]] = mult\n",
    "        return answer\n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        left=0\n",
    "        right=len(nums)\n",
    "        list1=[]\n",
    "        dict1={}\n",
    "        for i in range(right):\n",
    "            x=1\n",
    "            if nums[i] in dict1.keys():\n",
    "                list1.append(dict1.get(nums[i]))\n",
    "                continue\n",
    "            for j in range(right):\n",
    "                if i != j:\n",
    "                    x *= nums[j]\n",
    "            dict1[nums[i]] = x\n",
    "            list1.append(x)\n",
    "\n",
    "        return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [1] * n\n",
    "        left_product = right_product = 1\n",
    "        for i in range(n):\n",
    "            res[i] *= left_product\n",
    "            left_product *= nums[i]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            res[i] *= right_product\n",
    "            right_product *= nums[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        #anwer = []\n",
    "        product = 1\n",
    "        zero_count = 0\n",
    "        for num in nums:\n",
    "            if num!=0:\n",
    "                product *= num\n",
    "            elif zero_count==0:\n",
    "                zero_count+=1\n",
    "            else:\n",
    "                zero_count+=1\n",
    "                break\n",
    "        \n",
    "        length = len(nums)\n",
    "        if zero_count == 2:\n",
    "            return [0]*length\n",
    "        elif zero_count == 1:\n",
    "            for i in range(length):\n",
    "                if nums[i]!=0:\n",
    "                    nums[i]=0\n",
    "                else:\n",
    "                    nums[i] = product\n",
    "        else:\n",
    "            for i in range(length):\n",
    "                nums[i] = int(product/nums[i])\n",
    "        return nums\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        temp = 1\n",
    "        cn = Counter(nums)\n",
    "        if cn[0]>1:\n",
    "            return [0] * len(nums)\n",
    "        for n in nums:\n",
    "            temp *= n\n",
    "        res = []\n",
    "        for n in nums:\n",
    "            if n != 0:\n",
    "                res.append(temp//n)\n",
    "            else:\n",
    "                t = 1\n",
    "                for val in cn:\n",
    "                    if val != 0:\n",
    "                        t *= val**(cn[val])\n",
    "                res.append(t)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        if not nums:\n",
    "            return []\n",
    "        zero_num = nums.count(0)\n",
    "        if zero_num > 1:\n",
    "            return [0 for _ in nums]\n",
    "        elif zero_num == 1:\n",
    "            ind = nums.index(0)\n",
    "            new_nums = [0 for _ in nums]\n",
    "            nums[ind] = 1\n",
    "            new_nums[ind] = reduce(lambda x, y: x * y, nums)\n",
    "            return new_nums\n",
    "        else:\n",
    "            sum_total = reduce(lambda x, y: x * y, nums)\n",
    "            return [sum_total // one for one in nums]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        if n==1:return nums\n",
    "        if n==2:return nums[::-1]\n",
    "        zero_index = -1\n",
    "        zero_num = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            if num==0:\n",
    "                if zero_num==1:return [0]*n\n",
    "                zero_index = i\n",
    "                zero_num = 1\n",
    "        zero_ans = 1\n",
    "        if zero_num:\n",
    "            for i,num in enumerate(nums):\n",
    "                if i!=zero_index:\n",
    "                    zero_ans *= num\n",
    "            ans = [0]*n\n",
    "            ans[zero_index] = zero_ans\n",
    "            return ans\n",
    "        ans = [1]*n\n",
    "        pre = 1\n",
    "        for i in range(1,n):\n",
    "            pre *=nums[i-1]\n",
    "            ans[i] = pre\n",
    "        pre = 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            pre *= nums[i+1]\n",
    "            ans[i] *= pre\n",
    "        return ans\n",
    "            \n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        L,R,reslut = [0]*n,1,[0]*n\n",
    "\n",
    "        L[0]=1\n",
    "        for i in range(1,n):\n",
    "            L[i]=L[i-1]*nums[i-1]\n",
    "        \n",
    "        \n",
    "        for i in reversed(range(n)):\n",
    "            L[i]=L[i]*R\n",
    "            R=R*nums[i]\n",
    "\n",
    "\n",
    "        return L\n",
    "        \n",
    "\n",
    "       \n",
    "\n",
    "        return reslut\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [1] + [0]*(n-1)\n",
    "        R = 1\n",
    "        for i in range(1, n):\n",
    "            ans[i] = ans[i-1]*nums[i-1]\n",
    "        for i in reversed(range(n)):\n",
    "            ans[i] = ans[i]*R\n",
    "            R *= nums[i]\n",
    "        return ans\n",
    "\n",
    "        # 初始回答\n",
    "        # n = len(nums)\n",
    "        # answer, L, R = [0]*n, [0]*n, [0]*n\n",
    "        # L[0] = 1\n",
    "        # R[-1] = 1\n",
    "        # for i in range(1, n):\n",
    "        #     L[i] = L[i-1]*nums[i-1]\n",
    "        #     R[-i-1] = R[-i]*nums[-i]\n",
    "        # for i in range(n):\n",
    "        #     answer[i] = L[i]*R[i]\n",
    "        # return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [1]\n",
    "        for i in range(n - 1):\n",
    "            ans.append(nums[i] * ans[i])\n",
    "        for i in range(2, n + 1):\n",
    "            ans[-i] *= nums[-i + 1]\n",
    "            nums[-i] *= nums[-i + 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        ans = [1]\n",
    "        for i in range(len(nums)-1):\n",
    "            ans.append(nums[i] * ans[-1])\n",
    "\n",
    "        pre = nums[-1]\n",
    "        nums[-1] = 1\n",
    "        for i in range(len(nums)-2, -1, -1):\n",
    "            pre, nums[i] = nums[i], nums[i+1] * pre\n",
    "        print(ans, nums)\n",
    "        for i in range(len(ans)-1, -1, -1):\n",
    "            ans[i] = ans[i] * nums[i]\n",
    "\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        prefix_mul = [1] * n\n",
    "        postfix_mul = [1] * n\n",
    "        prefix_mul[0] = 1\n",
    "        postfix_mul[-1] = 1\n",
    "        for i in range(1, n):\n",
    "            prefix_mul[i] = nums[i-1] * prefix_mul[i-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            postfix_mul[i] = nums[i+1] * postfix_mul[i+1]\n",
    "            prefix_mul[i] = prefix_mul[i] * postfix_mul[i]\n",
    "        return prefix_mul"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        if not nums:\n",
    "            return []\n",
    "        \n",
    "        n = len(nums)\n",
    "        left_product = [1] * n\n",
    "        for i in range(1, n):\n",
    "            left_product[i] = left_product[i - 1] * nums[i - 1]\n",
    "        \n",
    "        right_product = 1\n",
    "        result = [1] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            result[i] = left_product[i] * right_product\n",
    "            right_product *= nums[i]\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        post = [1] *(n + 1)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            post[i] = post[i + 1] * nums[i]\n",
    "        \n",
    "        ans = [1] * (n + 1) \n",
    "\n",
    "        last = 1 \n",
    "        for i in range(1, n + 1):\n",
    "            ans[i] = last * post[i]\n",
    "            last *= nums[i - 1]\n",
    "        return ans[1:]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "      def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        pre = [1]*(n+1)\n",
    "        post = [1]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i]*nums[i]\n",
    "            post[n-i-1] = post[n-i]*nums[n-i-1]\n",
    "        return [pre[i]*post[i+1] for i in range(n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        n, l, r = len(nums), [0]*len(nums), [0]*len(nums)\n",
    "        l[0], r[n-1] = 1, 1\n",
    "        for i in range(1,n):\n",
    "            l[i] = l[i-1] * nums[i-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            r[i] = r[i+1] * nums[i+1]\n",
    "        for i in range(n):\n",
    "            nums[i] = r[i] * l[i]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        left, right = [1], [1]\n",
    "        length = len(nums)\n",
    "        for i in range(length-1):\n",
    "            left.append(left[-1]*nums[i])\n",
    "        for i in range(1, length):\n",
    "            right.append(right[-1]*nums[length-i])\n",
    "        res = []\n",
    "        for l, r in zip(left, right[::-1]):\n",
    "            res.append(l*r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        lnum = [0]*n\n",
    "        lnum[0] = 1\n",
    "        for i in range(1,n):\n",
    "            lnum[i] = lnum[i-1]*nums[i-1]\n",
    "        rnum = [0]*n\n",
    "        rnum[n-1] = 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            rnum[i] = rnum[i+1]*nums[i+1]\n",
    "        answer = [0]*n \n",
    "        for i in range(n):\n",
    "            answer[i] = lnum[i]*rnum[i]\n",
    "        return answer"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
